% Template for preprint document class `elsart5p'

\documentclass{elsart5p}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
%\usepackage{graphics}
% or use the graphicx package for more complicated commands
%\usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
%\usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
\usepackage{graphicx}

\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{booktabs}
\renewcommand{\algorithmicrequire}{\textbf{Input:}} % Use Input in the format of Algorithm
\renewcommand{\algorithmicensure}{\textbf{Output:}} % Use Output in the format of Algorithm

% The lineno packages adds line numbers. Start line numbering with
% \begin{linenumbers}, end it with \end{linenumbers}. Or switch it on
% for the whole article with \linenumbers.
% \usepackage{lineno}

% \linenumbers
\begin{document}

\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{Automatic Quad Patch Layout Extraction for Quadrilateral Meshes}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author{Submission ID: 101}
%\author{Anonymous Author 1}          % Important note: Anonymize your paper for double-blind reviewing!
                                     % Important note: Anonymize your paper for double-blind reviewing!
%\address{Anonymous Author's Address} % Important note: Anonymize your paper for double-blind reviewing!

\begin{abstract}

    In this paper, we present an automatic method to extract quad patch layout with monotone boundaries in a quadrilateral mesh.
    Our approach simplifies the separatrices and connectivity graph topologically compared with the previous work.
    The key idea of our method is firstly to find all the candidates of the ``short" separatrices based on the \emph{safety turning areas},
        and secondly, the problem of finding proper separatrices to extract quad patch layout is formulated as a binary integer programming problem.
    In the process of solving this problem, each solution is detected whether to extract quad patch layout,
        and finally the one with the minimum energy is determined as the global optimal solution.
    The produced quad patch layout is well-shaped and the corresponding base complex is coarse,
        which can be further used for many mesh processing applications, such as texturing, NURBS fitting and so on.

\end{abstract}

\begin{keyword}

    Quad Patch Layout, Safety Turning Area, Binary Integer Programming, Global Optimal Solution

\end{keyword}
\end{frontmatter}

% main text
\section{Introduction}
\label{sec:introduction}

    Quadrilateral mesh (quad mesh for short) is one of the most popular shape representations in computer graphics,
        which is widely used in CAD/CAM, numerical simulation and other areas.
    Among quad meshes, semi-regular ones, which have few number of irregular vertices,
        has been gained more attentions~\cite{Bommes:2013:QGP}.
    Significant progress has been made in generation and processing of quad meshes during the last decades.

    However, most semi-regular quad mesh generation algorithms focus on
        minimizing the number of the irregular vertices and the shape of the quads.
    When analyzing the global structure of the generated quad meshes,
        as it is depicted in Fig~\ref{fig:generation:layoutcompare}(a),
        they do not exhibit a coarse and well-shaped patch layout.
    In practice, such a coarse patch layout (seen in Fig~\ref{fig:generation:layoutcompare}(b)) is highly desirable to support operations
        such as texturing, adaptive sizing and so on.

    \begin{figure}[tcb]
        \centering
        \includegraphics[width=\linewidth]{Figures/layoutcompare}
        \caption{\label{fig:generation:layoutcompare}
            Comparison of different patch layouts with the same number of irregular vertices.
            (a) There are many crossings (blue points) in the patch layout, and the resulted patch layout is dense.
            (b) An optimal quad patch layout with small number of patches.}
    \end{figure}

    In this paper, based on simplifying the separatrices and the connectivity graph,
        we present an automatic method to extract a coarse and well-shaped quad patch layout in a quad mesh.
    The key idea is to firstly find all the candidates of the ``short" separatrices in the quad mesh based on \emph{safety turning areas},
        and then with the help of a binary integer programming solver,
        globally minimized the total energy of the selected separatrices until they could extract a quad patch layout.
    Fig~\ref{fig:generation:processing} provides a quick overview over the stages of the procedure.
    
    \begin{figure*}[tcb]
        \centering
        \includegraphics[width=\linewidth]{Figures/processing}
        \caption{\label{fig:generation:processing}
            Main steps of the proposed algorithm.
            Fandisk model is shown in Fig(a); The initial separatrices (red lines) is shown in Fig(b);
            Fig ($c_1$) - Fig ($c_4$) are an example to find all possible separatrices related to one port (blue arrows),
            where the other ports which is connected by the separatrices are shown in blue lines,
                the irregular vertices related to the separatrices are shown in purple points,
                the boundaries of the \emph{safety turning area} are shown in red lines,
                and the geodesic paths in the \emph{safety turning area} are shown in green lines.
            The desired patch layout with the minimal energy is shown Fig (d), in which the boundaries are shown in colored lines.}
    \end{figure*}

    The main contributions of this paper are as follows.

    \begin{itemize}
    \item [-] All ``short" separatrices can be found following an area-growing strategy.
        Further more, since the separatrices in the same \emph{safety turning area} connect the same irregular vertices through the same ports,
        and they share a common and minimum energy,
        only one of them will be selected to be a candidate, which greatly deduce the number of ``short" separatrices.\\
        The candidate in a \emph{safety turning area} satisfies the monotone constraint and achieves the minimal energy.
    \item [-] We formulate the problem of finding the proper candidate separatrices to extract quad patch layout as a binary integer programming problem.\\
        Compared with the method by a greedy strategy,
        it efficiently avoids obtaining partial optimal solutions and enables us to find the global optimal solution.
    \item [-] With the help of the geodesic path,
        a simple but efficient method is used to quickly determine whether a solution of the binary programming problem can extract quad patch layout.
    \end{itemize}

\subsection{Related work}

    Generally speaking, there are two main types of methods for extracting the quad patch layout of a quad mesh:
        one type is based on mesh segmentation,
        and the other is based on simplifying separatrices and connectivity graph.
    The reader is referred to \cite{Bommes:2013:QGP} for a more comprehensive survey of the quad mesh processing.

    \quad

    \textbf{Mesh Segmentation.} Vieira and Shimada~\cite{Vieira:2005:SMS} segmented the mesh while iterating
        between region growing and surface fitting.
    \cite{Benko:2002:DSS}, \cite{Cohen:2004:VSA} and~\cite{Wu:2005:SRH} all segmented
        the mesh with the help of geometric measure.
    Benk{$\ddot{o}$} and V{\'a}rady~\cite{Benko:2002:DSS} segmented the mesh by approximating each patch by geometrical primitives.
    Cohen-Steiner et al.~\cite{Cohen:2004:VSA} drove the distortion error down through repeated clustering
        using the concept of geometric proxies.
    Wu and Kobbelt~\cite{Wu:2005:SRH} extended this method by allowing
        planes, spheres, cylinders and rolling-ball blend patches.
    Myles et al.~\cite{Myles:2010:FAT} used a greedy algorithm to generate coarse quadrilateral patches
        which were appropriate to fit with T-splines.
    Eppstein et al.~\cite{Eppstein:2008:MGC} partitioned the mesh into
        structured quadrilateral patches with the help of motorcycle graph proposed in~\cite{Eppstein:1999:RCP}.
    Gunpinar et al.~\cite{Gunpinar:2013:GBP} extended the motorcycle graph, and with the help of a patch growing strategy,
       the bi-monotone patches were achieved.
    
    However, the methods based on mesh segmentation might change the number and distribution of the irregular vertices,
        which could bring in some deformation distortions during extracting patch layout.

    \quad

    \textbf{Separatrices and Connectivity Graph Simplification.} Bommes et.al~\cite{Bommes:2011:GSO} used GP-Operators,
        which were the generalization of the poly-chord collapse operations,
        to greedily simplify the local helical quadrilateral structures,
        and what was more, each simplification process changed the local quadrilaterals
        while maintaining quad-consistency as well as irregular vertices.
    Then they used a convex mixed-integer quadratic programming formulation~\cite{Bommes:2013:IMRQM} to generate reliable quad mesh,
        which could achieve high-quality coarse quad layout by globally searching.

    Campen et al.~\cite{Campen:2012:SQD} proposed the algorithm which was consisted in the direct construction of a simple connectivity out of a prescribed cross-field.
        In the algorithm, a simple operator was used in the process to greedily add a candidate ``dual-loop"
        to generate a quadrilateral mesh which reproduced the cross-field's singularities,
        and it produced a good base complex of the mesh.

    Li et al.~\cite{Li:2011:SOQME} used two global operations, ``re-sampling" and ``re-distribution", to optimize the shape of the patch layout in quad mesh,
        and finally make the mesh possess, as much as possible.
    Peng et al. proposed a connectivity editing framework for quad~\cite{Peng:2011:CEQ} and quad-dominant~\cite{Peng:2013:CEQDM} meshes,
        which allowed user to edit mesh connectivity by controlling the number and distribution of the irregular vertices and irregular faces,
        and then they could illustrate the advantages and disadvantages of different strategies for quad/quad-dominant mesh design.

    Tarini et al.~\cite{Tarini:2011:SQD} used two atomic operators, ``delete" and ``open" moves, to
        disentangle the separatrices and connectivity graph by selecting separatrices
        that were as ``short" as possible.
    Once the energy of all separatrices could not be deduced,
        the patch layout of the quadrilateral mesh is generated.
    In the algorithm, the separatrices were selected by a depth-first searching method,
        and although in practice, the produced structure dramatically improved over the input graph,
        the strategy was greedy and in theory it can not guarantee to get the most optimized result.
    Besides, the possible operations were high coupling with the energy defined on separatrices in this method,
        once the energy definition was changed,
        it needs to re-detect all possible operations and lead to a high time consuming.

    The methods based on simplifying separatrices and connectivity graph mostly maintained the consistency of the irregular vertices,
        but they used a greedy strategy to select the redirected separatrices,
        which might obtaining partial optimal solutions instead of the global optimal solution.

    \quad

    The rest of the paper is organized as follows.
    Some problem definitions are listed in Section~\ref{sec:definition},
    safety turning areas and their candidate are found in Section~\ref{sec:detection}.
    A binary integer programming problem of finding the proper separatrices to extract quad patch layout is introduced in Section~\ref{sec:optimization}.
    Experiments are shown in Section~\ref{sec:applications},
        and future work is discussed in Section~\ref{sec:conclusion}.

\section{Problem Definitions}
\label{sec:definition}

    A quad mesh embedded in 3D can be represented as $M = (V, E, Q)$,
        where $V$ is the set of vertices, $E$ is the set of edges and $Q$ is the set of quads.
    Given a closed quad mesh, a vertex is regular if and only if its valance is 4, otherwise it is \emph{irregular}.

    Topologically a regular vertex is the crossing of two coordinate lines in a 2D Cartesian grid
        and therefore a right-hand local coordinate system could be built
        in counter-clockwise order with $u$, $v$, $-u$, $-v$~\cite{Bommes:2011:GSO}
        as depicted in Fig~\ref{fig:generation:definition:uvlines}.

    \quad

    \begin{figure}[tcb]
        \centering
        \includegraphics[width=0.9\linewidth]{Figures/uvlines}
        \caption{\label{fig:generation:definition:uvlines}
            A right-hand local coordinate system with $u$~(purple arrow), $v$~(cyan arrow), $-u$~(yellow arrow), $-v$~(green arrow) built at a regular vertex.
            Ports at an irregular vertex are shown as blue arrows.
            A separatrix is shown as a red line.}
    \end{figure}

    \begin{description}
    \item [Port] A port is the outgoing edge adjacent to an irregular vertex (seen in Fig~\ref{fig:generation:definition:uvlines}).
        An irregular vertex of valency $n$ has $n$ distinct ports.
    \end{description}

    \quad

    \begin{description}
    \item [Separatrix] A separatrix contains a directed edge sequence
        and two endpoints which are restrained to be irregular vertices (seen in Fig~\ref{fig:generation:definition:uvlines}).
        The inner vertices passed by the separatrix are all regular.
    \end{description}

    \quad

    Typically, the edge sequence of an \emph{initial separatrix} starts from a port of an irregular vertex,
        followed by the edge of a regular vertex in the same local parametric direction, i.e., they are either $\{u,-u\}$ or $\{v,-v\}$,
        and ends at an irregular vertex~(maybe the same irregular vertex as the start vertex).

    \quad

    \begin{description}
    \item [Connectivity Graph] If every port of any irregular vertex is associated with a particular separatrix,
        all separatrices and their crossings form a connectivity graph of the quad mesh.
    \end{description}

    \quad

    Considering the separatrices as the boundaries of the patches, one connectivity graph segments the quad mesh into
        a patch layout~(see in Fig~\ref{fig:generation:layoutcompare}).

    Obviously, since the corners in the patch layout are either irregular vertices or the crossings of the separatrices,
        and the number of irregular vertices is the intrinsic property of a quad mesh,
        the complexity of the patch layout is directly determined by the number of crossings.
    At the same time, as a long separatrix has a greater probability of generating crossings,
        finding ``short" separatrices in the quad mesh and using them to form the connectivity graph
        can help us to deduce the number of the crossings and further to achieve a coarse and well-shaped patch layout.

    What is more, because a quad topology of the mesh is more preferred in many applications,
        we focus on extract a quad patch layout.
        
    A patch layout is called \emph{quad} if and only if every patch in it is bounded by four different separatrices.

    \begin{figure}[tcb]
        \centering
        \includegraphics[width=\linewidth]{Figures/safetyturningarea}
        \caption{\label{fig:generation:detectoin:safetyturningarea}
            In (a), the rectangle area, which is bounded by purple lines,
                and the ports ($e_0^0, e_0^1$) (shown in blue arrows),
                which have the same local parametric direction and connect the rectangle area at the bottom-left and top-right corners respectively,
                can form a safety turning area.
            Likewise, ports ($e_1^0, e_1^1$), ($e_2^0, e_2^1$) and ($e_3^0, e_3^1$) can also form valid safety turning areas
                with the rectangle area respectively.}
    \end{figure}

    \quad

    \begin{description}
    \item [Safety Turning Area] A safety turning area is the combination of a rectangle area in the quad mesh and two ports of irregular vertices.
        The vertices in the rectangle area are all regular.
        The two ports (called ``diagonal ports") connect the rectangle area at the diagonal corners and have the same local parametric direction.
    \end{description}

    \quad

    All four types of safety turning area are shown in Fig~\ref{fig:generation:detectoin:safetyturningarea}.
    There are two main reasons for the definition of safety turning area:

    \begin{enumerate}
    \item Considering the separatrices in a safety turning area, ``safety turning" means that the edge sequence could be freely changed in the rectangle area,
        since there is no irregular vertex in it.
    \item That the diagonal ports have the same local parametric direction makes the separatrices in the safety turning area along the local direction of the cross field,
        which efficiently deduces the probabilities of forming non-quad patches.
    \end{enumerate}

    \begin{figure}[tcb]
        \centering
        \includegraphics[width=\linewidth]{Figures/monotone}
        \caption{\label{fig:generation:detectoin:monotone}
            The red points in the figure are denoted as irregular vertices,
            and the green quads form the rectangle area of the safety turning area.
            In (a) and (b), the edges of separatrices (yellow lines) in the rectangle area are not monotone in ``x-dir" and ``y-dir" respectively.
            In (c) and (d), the separatrices (blue lines and yellow lines) satisfy both x-monotone and y-monotone constraints.
            Although the edge sequences of separatrices are different in (c) and (d),
                they have the same and minimal length.}
    \end{figure}

    \quad

    Supposing that in the rectangle area of a safety turning area,

    \begin{itemize}
    \item Along the local parametric direction (called ``x-dir") of the port, the length of the rectangle area is $L_{wid}$;
    \item Along the orthogonal parametric direction (called ``y-dir") of the port, the length of the rectangle area is $L_{ext}$;
    \end{itemize}

    \quad
    
    For a port in the quad mesh, if the rectangle areas appear at the left part of its ``x-dir", the corresponding safety turning areas are called \emph{left},
        otherwise, if the rectangle areas appear at the right, the safety turning areas are called \emph{right}.

    For example, for port $e_0^0$, the safety turning area in the Fig~\ref{fig:generation:detectoin:safetyturningarea}(a) is a left safety turning area,
        since the rectangle area appears at the left part of the ``x-dir" of port $e_0^0$;
        and for port $e_3^0$, the safety turning area in the Fig~\ref{fig:generation:detectoin:safetyturningarea}(b) is a right safety turning area,
        since the rectangle area appears at the right part of the ``x-dir" of port $e_3^0$.
        
    \quad

    Considering the edge sequence of the separatrices in the rectangle area,

    \begin{itemize}
    \item If the number of the edges is one for every column(i.e., the edges in a separatrix and parallel to ``x-dir"),
        the separatrix is called \emph{x-monotone}.
    \item If the number of edges is one for every row(i.e., the edges in a separatrix and parallel to ``y-dir"),
        the separatrix is called \emph{y-monotone}.
    \end{itemize}

    A \emph{monotone} separatrix satisfies both the x-monotone and y-monotone constraints, seen in Fig~\ref{fig:generation:detectoin:monotone}.

    \quad

    We assume the input quad mesh have uniform edge length,
        such that the $L_{wid}$ and $L_{ext}$ of the rectangle area
        and the length of separatrix
        can be simply measured by the number of the edges in the edge sequence.
    
    Take the safety turning area associated to ports ($e_0^0, e_0^1$) in the Fig~\ref{fig:generation:detectoin:safetyturningarea}(a) as an example,
        the $L_{wid}$ is 2 and $L_{ext}$ is 3.

    Note that if the $L_{wid}$ is 0, the separatrix is just an \emph{initial separatrix}.

    \quad\\
    Theory 1: \emph{In a safety turning area,
        only the monotone separatrices could be considered as the desired ``short" separatrices,
        and one of the monotone separatrices can be selected to be a candidate for others.}

    In a safety turning area, although there are many separatrices connecting the irregular vertices through the diagonal ports,
        only the monotone separatrices pass exactly ``extension" times of column edges and ``width" times of row edges
        (i.e. the number of edges in the rectangle area is exactly $L_{wid} + L_{ext}$).
    Otherwise, if the separatrix is not monotone, the number of edges in the rectangle area is more than $L_{wid} + L_{ext}$,
        which does not satisfy the requirement of ``short" separatrices.
    Consequently, only the monotone separatrices could be considered as the desired ``short" separatrices.

    What is more, since all monotone separatrices connect the same irregular vertices through the same ports,
        and their length are the same (i.e. $L_{wid} + L_{ext} + 2$),
        which is minimum and determined only by the intrinsic properties of the rectangle area,
        one of them could be selected to be a candidate for others.

\section{Safety Turning Area Detection}
\label{sec:detection}

    As the discussion above, in order to extract a quad patch layout,
        all ``short" separatrices should be found in the quad mesh.
    
    A naive method is firstly to find all separatrices in the quad mesh,
        and then after removing the ``longer" ones from them,
        the rest separatrices are ``short".
    However, the number of all separatrices is so huge that they are unable to be enumerated.

    Fortunately, since one of the monotone separatrices can be selected to be a candidate for all other ``short" separatrices in a safety turning area,
        the problem of finding all ``short" separatrices could be transformed into finding all safety turning areas.

    For each port of the quad mesh, we could find all ``short" separatrices related to it by an area-growing strategy, seen in Algorithm~\ref{algorithm:findsafetyturningarea}.

    \begin{figure}[tcb]
        \centering
        \includegraphics[width=\linewidth]{Figures/safetyareadetection}
        \caption{\label{fig:generation:safetyareadetection}
            The red points in the figure are denoted as irregular vertices,
            and the green quads form the rectangle area of the safety turning area.
            (a) is corresponding to add a left safety turning area,
            and (b) is corresponding to add a right safety turning area.}
    \end{figure}

    \begin{algorithm}[h]
    \caption{Find all safety turning areas related to a port}
    \label{algorithm:findsafetyturningarea}
    \begin{algorithmic}[1]
    \Require Port $e_{start}$; The set of all safety turning area $S$;
        The max length for width $WID_{max}^{left}$, $WID_{max}^{right}$;
        The max length for extension $EXT_{max}$;
    \Ensure $S$
    \State Initialize $S=\phi$; $EXT_{max}^{left} = EXT_{max}$; $EXT_{max}^{right} = EXT_{max}$
    \State $e_{end}^{left}$ and $e_{oend}^{left}$ are the ``top-right" edges seen in Fig~\ref{fig:generation:safetyareadetection}(a)
    \State $e_{end}^{right}$ and $e_{oend}^{right}$ are the ``bottom-right" edges seen in Fig~\ref{fig:generation:safetyareadetection}(b)\\
    \State $//$ Find all left safety turning areas.
    \For{$i = 0$; $i \leq WID_{max}^{left}$; $i++$}
        \For{$j = 1$; $j < EXT_{max}^{left}$; $j++$}
            \If{$e_{end}^{left}$ points to an irregular vertex}
                \State $EXT_{max}^{left} = j + 1$;
                \State Add a left safety turning area to $S$:
                \State \{ Ports are $e_{start}$ and $e_{oend}^{left}$, 
                \State $L_{wid} = i$, $L_{ext} = j - 1$\};
            \EndIf
        \EndFor
    \EndFor\\
    \State $//$ Find all right safety turning areas.
    \For{$i = 0$; $i \leq WID_{max}^{right}$; $i++$}
        \For{$j = 1$; $j < EXT_{max}^{right}$; $j++$}
            \If{$e_{end}^{right}$ points to an irregular vertex}
                \State $EXT_{max}^{right} = j + 1$;
                \State Add a right safety turning area to $S$:
                \State \{ Ports are $e_{start}$ and $e_{oend}^{right}$, 
                \State $L_{wid} = i$, $L_{ext} = j - 1$\};
            \EndIf
        \EndFor
    \EndFor
    \end{algorithmic}
    \end{algorithm}

    \quad

    It should be noted that once the growing area meets an irregular vertex,
        we reduce the max length of the extension(i.e. $EXT_{max}^{left}$ and $EXT_{max}^{right}$ are reduced).
    The reason is that for the irregular vertices which are far away (e.g. the irregular vertices in the yellow area in Fig~\ref{fig:generation:breakreason}),
        although there maybe exist some possible separatrices to connect them with the start port $e_{start}$,
        another ``shorter" separatrices are more preferred to be chosen, seen in Fig~\ref{fig:generation:breakreason}.

    \begin{figure}[tcb]
        \centering
        \includegraphics[width=\linewidth]{Figures/breakreason}
        \caption{\label{fig:generation:breakreason}
            The reason to reduce the max length of the extension when the growing area meets an irregular vertex.
            An far away irregular vertex appears in the yellow area in (b)
            There exist possible separatrices to connect it with the start port, one of them is shown as the purple lines in (c).
            Better separatrices which are composed of two ``shorter" separatrices in the safety turning area are shown in (d).}
    \end{figure}

    \quad
    
    In the Algorithm~\ref{algorithm:findsafetyturningarea}, the max length for width ($WID_{max}^{right}$ and $WID_{max}^{left}$)and extension ($EXT_{max}^{right}$) should to be carefully chosen,
        because a small value could result in missing some valid ``short" separatrices,
        and a big value could increase the number of ``short" separatrices to reduce the efficiency of further binary integer programming.

    Similar to the reason of reducing the max length of extension,
        if the irregular vertices appear in the yellow areas in the Fig~\ref{fig:generation:maxvalue} (a), (b), (c),
        better separatrices which are ``shorter" exist and are more preferred.

    \begin{figure}[tcb]
        \centering
        \includegraphics[width=\linewidth]{Figures/maxvalue}
        \caption{\label{fig:generation:maxvalue}
            In (a), (b), (c), the possible separatrices (shown in green dash lines) starts from $e_{start}$ to the irregular vertices in the yellow areas
                are not ``short" enough (better separatrices are shown in purple dash lines), so they could not be selected to be the ``short" separatrices.
            The $EXT_{max}$ and $WID_{max}^{left}$ are shown in (d).
            }
    \end{figure}

    Consequently, $EXT_{max}$ will be set to be the length of the initial separatrix from the start port $e_{start}$, seen in Fig~\ref{fig:generation:maxvalue}(d).
    $WID_{max}^{left}$ is set to be the length of the initial separatrix, whose start port is the left neighbor of $e_{start}$,
    and $WID_{max}^{right}$ is set to be the length of the initial separatrix, whose start port is the right neighbor of $e_{start}$.

\section{Binary Integer Programming Problem}
\label{sec:optimization}

    As discussed above, the separatrices in a safety turning area
        share a common length ($L_{wid} + L_{ext} + 2$), which is only determined by the intrinsic properties of the rectangle area.
    So a simple way to define the energy $E$ of a ``short" separatrix could measure its length, i.e. $E = L_{wid} + L_{ext} + 2$.

    However, although the safety turning areas help us to find ``short" separatrices,
        the founded ``short" separatrices are misaligned to the local cross field in the quad mesh,
        since they turn $L_{wid}$ times in the rectangle areas.
    In order to punish the misalignment,
        weighed coefficients are added into the definition of the energy of a separatrix.
    For a separatrix $P_i$, its energy is defined as Equation~\ref{equ:energy}.

    \begin{equation}
    \label{equ:energy}
        E(P_i) = L_{ext} + 2 + \alpha \times L_{wid} \quad (\alpha \geq 1)
    \end{equation}

    Gathering all candidates selected from the corresponding safety turning areas,
        the problem of extracting quad patch layout can be formulated into
        a binary integer programming problem.
    In this problem, our goal is to minimized the energy of the connectivity graph.
    At the same time, there are two constraints should be satisfied.

    \quad

    \begin{enumerate}
    \item In the connectivity graph, every port in the quad mesh should exactly associated with only one separatrix.
    \item The extracted patch layout should be quad, i.e. every patch should be bounded by exactly four different separatrices.
    \end{enumerate}

    \quad

    Suppose the number of ports in the quad mesh is $m + 1$, and the set of all separatrices is $S = \{P_0,\dots,P_n\}$.

    For any port~$e_i (0 \leq i \leq m)$, suppose the number of separatrices related to it is $m^i + 1$,
        then $S_i = \{n_i^0, n_i^1, \dots, n_i^{m^i}\}$ is the set of indices of separatrices,
        where $P_{n_i^j} (0 \leq j \leq m^i)$ is a separatrix in $S$ and related to $e_i$.

    By using $a_t (0 \leq t \leq n)$ to represent the corresponding separatrix whether to be selected(
        i.e. $a_t = 1$ means the separatrix $P_t$ is selected; otherwise, $a_t = 0$ means it is not selected),
        the first constraint for port $e_i$ can be represented as $\sum\limits_{j = 0}^{m^i}a_{S_i[j]} = 1$.

    Consequently, the binary integer programming problem can be defined as Equation~\ref{equ:binary}:

    \begin{eqnarray}
    \label{equ:binary}
        Min \quad E_G & = & \sum\limits_{t=0}^{n}{a_tx_t} \nonumber\\
        s.t. \sum\limits_{j = 0}^{m^i}a_{S_i[j]} & = & 1, \qquad 0 \leq i \leq m \\
             a_t & \in & \{0,1\}, 0 \leq t \leq n \nonumber \\
             x_t & = & E(P_t), 0 \leq t \leq n \nonumber
    \end{eqnarray}

    By solving the binary integer programming problem, a patch layout with minimum energy could be extracted.
    However, the resulted patch layout can not guarantee achieving quad topology.
    Actually, for a large number of cases, the patch layout does contain many non-quad patches.

    The main reasons to produce non-quad patches are
    \begin{enumerate}
    \item a wrong combination of separatrices are selected and
    \item the separatrices which are candidates selected from the corresponding safety turning areas may pass improper edge sequences to produce some unnecessary crossings.
    \end{enumerate}

    \begin{figure}[tcb]
        \centering
        \includegraphics[width=\linewidth]{Figures/badcandadite}
        \caption{\label{fig:generation:badcandadite}
            In (c) and (d), the blue lines are the candidate separatrix selected from the safety turning area in (a),
                and the purple lines are the candidate separatrix selected from the safety turning area in (b).
            However, the red quads in (c) and red lines in (d) create a wrong the topology of the patch layout.
            For these two safety turning areas, proper selection of candidates is shown in (e).
            Instead of analyzing the safety turning areas to select proper edge sequences,
            geodesic path in the rectangle areas is used to analyze the patch topology in (f).
            }
    \end{figure}

    For the former reason, we could simply exclude the solution,
        and resolve the binary integer programming problem to get another global optimal solution.
    
    For the latter, an improper selection of candidates may result in some unnecessary crossings to produce non-quad patches in Fig~\ref{fig:generation:badcandadite} (c),
        or even worse, the edges in the separatrices are overlapped in Fig~\ref{fig:generation:badcandadite} (d).
    An good solution to overcome these shortcomings is to analyze the intersection parts of the safety turning areas to find a proper edge sequence,
        as shown in Fig~\ref{fig:generation:badcandadite}(e),
        however, this analysis is so complicated that many special cases should be considered.

    In our algorithm, we use a simple but efficient method to deal with the latter problem.
    Since the edge sequence of candidate separatrices is only used to analyze the topology of the patch,
        we could use the geodesic path in the rectangle area instead of the edge sequence to be the boundaries to do the same analysis, seen in Fig~\ref{fig:generation:badcandadite}(f).
    
    When computing the geodesic path, we only take the quads and vertices in the rectangle areas into account,
        so the path to connect the related ports of the corresponding safety turning area can be efficiently achieved.
    Our experiments demonstrate that using geodesic path, instead of edge sequence to analyze the topology of patch layout
        is robust and efficiently.

    \quad

    Besides, to solve the binary integer programming problem,
        almost all the solvers are based on the ``branch-to-cut" strategy,
        and once they meet a minimized solution, the result is returned and the solvers stop.
    Although the result is good and globally optimized,
        it will miss some other global optimal solutions with the same minimum energy.
    So when we solve the problem, in order to achieve all the global optimal solutions,
        once we get a result, it will be stored and an energy constraint,
        which asks the energy of the problem to be exactly equal to current minimum energy,
        is added into the problem, seen in Fig~\ref{fig:generation:equationenergy}.
    If all the global optimal solutions for current minimum energy are found,
        but they can not extract a quad patch layout,
        the energy constraint is relaxed to find further results.
        
    The entire algorithm for the binary integer programming is shown in Algorithm~\ref{alg:generation:all}.

\begin{algorithm}[h]
    \caption{Extract quad patch layout in a quad mesh}
    \label{alg:generation:all}
    \begin{algorithmic}[1]
    \Require All ``short" separatrices which are the candidates of the safety turning areas
    \Ensure Quad patch layout
    \State Construct the binary integer programming problem.
    \Repeat
    \State Find one global optimal solution.
    \State Try to extract quad patch layout.
    \If {Failed to extract}
        \State Add the energy constraint
        \Repeat
            \State Find one global optimal solution.
            \If {The global optimal solution is found}
                \State Try to extract quad patch layout.
                \If {Failed to extract}
                    \State Add the energy constraint.
                \Else
                    \State \Return the quad patch layout;
                \EndIf
            \Else
                \State Relaxed the energy constraint.
            \EndIf
        \Until{The energy constraint is relaxed}
    \Else
        \Return the quad patch layout;
    \EndIf
    \Until{Extracting quad patch layout}
    \State \Return the quad patch layout;
    \end{algorithmic}
    \end{algorithm}
    
    \begin{figure}[tcb]
        \centering
        \includegraphics[width=\linewidth]{Figures/equationenergy}
        \caption{\label{fig:generation:equationenergy}
            (a), (b), (c) have the same energy but a different connectivity graph.
            }
    \end{figure}

    \quad

    Because the binary integer programming problem is NP-hard,
        and we want to find the global optimal solutions,
        it needs us to deduce the scale of the problem to speed up.

    Seen in Fig~\ref{fig:generation:detectoin:safetyturningarea} (a),
        when the safety turning areas for port $e_0^0$ are detected,
        the safety turning area shown in green is added as a left safety turning area.
    At the same time, during finding the safety turning areas for port $e_0^1$, the same turning area
        is added again.
    Consequently, before formulating the problem into the binary integer programming problem,
        the duplicated safety turning areas should be removed and only one of them is left.
    Table~\ref{tab:generation:optimization:preprocessing} shows that this preprocessing deduces nearly 50\% scale of the problem,
    In the table, $N_F$ is the number of quads, $N_V$ is the number of vertices in the quad mesh,
        $N_{Base}^{S}$ is the number of safety turning areas before removing duplicated ones,
        and $N_{Opt}^{S}$ is the number of safety turning areas after removing.

    \begin{table}[tcb]
    \centering
    \caption{Before and after preprocessing}
    \label{tab:generation:optimization:preprocessing}
    \begin{tabular}{rcccc}
    \toprule
        Model & $N_F$ & $N_V$ & $N_{Base}^{S}$ & $N_{Opt}^{S}$\\
    \midrule
        CubeBlob~[Fig\ref{fig:generation:layoutcompare}] & 9146 & 9148 & 2132 & 989\\
        Cup~[Fig\ref{fig:application:cupvsd}] & 14983 & 14981 & 1008 & 473\\
        Joint~[Fig\ref{fig:application:totalvsd}(c2)] & 8804 & 8802 & 728 & 359\\
        Fandisk~[Fig\ref{fig:application:totalvsd}(a2)] & 3056 & 3058 & 821 & 403\\
        Hole3~[Fig\ref{fig:application:totalvsd}(e2)] & 36487 & 36483 & 1928 & 927\\
        Igea~[Fig\ref{fig:application:totalvsd}(b2)] & 8183 & 8185 & 771 & 382\\
        Rockeram~[Fig\ref{fig:application:totalvsd}(d2)]& 9413 & 9413 & 1402 & 708\\
    \bottomrule
    \end{tabular}
    \end{table}

    \quad
    
    What is more, if the number of the ``short" separatrices related to a port is 1,
        this separatrix must be selected,
        and it is unnecessary to appear as an variable in the binary integer programming problem.

\section{Experiments}
\label{sec:applications}

    In our experiments, the input quad meshes are generated by mixed-integer quadrangulation~\cite{Bommes:2009:MIQ},
        which results uniform edge length as required by our method.

    The environment of our experiments is Intel(R) Core(TM) i5 CPU @ 3.00GHZ and 3.2GHZ,
        16G RAM Memory and the binary integer programming optimizer are provided by function ``bintprog" in Mosek.
    Some models with quad patch layout are shown in
        Fig~\ref{fig:application:totalvsd} and \ref{fig:application:cupvsd}.
    The time used by our method is shown in Table~\ref{tab:application:time},
        in which $T_{Det}$ represents the time used by detecting safety turning areas in mesh,
        $N_{Opt}$ represents the number of binary integer programming calculated during the globally optimization,
        and $T_{Opt}$ represents the total time used by binary integer programming optimizer.

    \begin{figure*}[tcb]
        \centering
        \includegraphics[width=\linewidth]{Figures/totalvsd}
        \caption{\label{fig:application:totalvsd}
            (a1) and (a2) are Fandisk model, the number of quad patches is 52;
            (b1), (b2) and (b3) are Igea model, the number of quad patches is 28;
            (c1) and (c2) are Joint model, the number of quad patches is 41;
            (d1) and (d2) are Rockarm model, the number of quad patches is 67;
            (e1) and (e2) are Hole3 model, the number of quad patches is 20;}
    \end{figure*}

    \begin{figure}[htb]
        \centering
        \includegraphics[width=\linewidth]{Figures/cupvsd}
        \caption{\label{fig:application:cupvsd}
            Cup model,  the number of quad patches produced by~\cite{Tarini:2011:SQD} is 25, shown in (d),
            while the number of quad patches extracted by our method is 23, shown in (b) and (c).}
   \end{figure}

    \begin{table}[htb]
    \centering
    \caption{Time consuming}
    \label{tab:application:time}
    \begin{tabular}{rccc}
    \toprule
        Model & $T_{Det}(s)$ & $N_{Opt}$ & $T_{Opt}(s)$\\
    \midrule
        CubeBlob~[Fig\ref{fig:generation:layoutcompare}] & 0.057 & 1 & 0.16\\
        Fandisk~[Fig\ref{fig:application:totalvsd}(a2)] & 0.022 & 2 & 0.21\\
        Hole3~[Fig\ref{fig:application:totalvsd}(e2)] & 0.499 & 1 & 0.15\\
        Igea~[Fig\ref{fig:application:totalvsd}(b2)] & 0.106 & 42 & 4.32\\
        Rockeram~[Fig\ref{fig:application:totalvsd}(d2)]& 0.093 & 43 & 7.95\\
        Joint~[Fig\ref{fig:application:totalvsd}(c2)] & 0.047 & 291 & 227.5\\
        Cup~[Fig\ref{fig:application:cupvsd}] & 0.284 & 519 & 573.1\\
    \bottomrule
    \end{tabular}
    \end{table}

    As seen in Fig~\ref{fig:application:cupvsd}, our method could find the global optimal connectivity graph to extract quad patch layout,
        and the number of quad patches is smaller than the number produced by~\cite{Tarini:2011:SQD}.
    Compared with their method, we use a similar energy definition for separatrices,
        but based on the safety turning area,
        we make enumerating all ``short" separatrices possible.
    And then by solving the binary integer programming problem, the final solution could be guaranteed to be the global optimal solution .
    It overcomes the main shortcomings of the greedy strategy used by others,
        which may fall into obtaining local optimal solution.

\section{Conclusion and Future Work}
\label{sec:conclusion}

    In this paper, an automatic method is proposed to extract wells-shaped quad patch layout with monotone boundaries in quad meshes.
    Based on safety turning area, all ``short" separatrices in the quad mesh could be found at first,
        and then the global optimal solution could be achieved by a binary integer programming optimizer,
        which efficiently avoid the problem falling into obtaining local optimal solution.
    At the same time, with the help of the geodesic path,
        we are able to quickly determine whether a solution of the binary integer programming problem can extract quad patch layout.

    However, as the binary integer programming problem is NP-Hard which can not be solved in polynomial time,
        time consuming is the main limitation of our method.
    Consequently, the main future work is to speed up the convergence efficiency,
        or to find a proper constraint of quad topology which can be added into the binary integer programming problem directly.
    At the same time, how to extend our method to deal with open quad meshes is also our future work.

% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
% \appendix

% \section{}
% \label{}

\begin{thebibliography}{00}

% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}

\bibitem{Myles:2010:FAT}
    Ashish Myles and Nivo Pietroni and Denis Kovacs and Denis Zorin, Feature-aligned T-meshes, ACM Transactions on Graphics, 29, 117 (2010)
\bibitem{Peng:2011:CEQ}
    Chi-Han Peng and Eugene Zhang and Yoshihiro Kobayashi and Peter Wonka, Connectivity Editing for Quadrilateral Meshes, ACM Transactions on Graphics, 30, 141:1-141:12 (2011)
\bibitem{Peng:2013:CEQDM}
    Chi-Han Peng and Peter Wonka, Connectivity Editing for Quad-Dominant Meshes, Computer Graphics Forum, 32, 43-52 (2013)
\bibitem{Eppstein:1999:RCP}
    David Eppstein and Jeffrey Gordon Erickson, Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions, Discrete and Computational Geometry, 22, 569-592 (1999)
\bibitem{Cohen:2004:VSA}
    David Cohen-Steiner and Pierre Alliez and Mathieu Desbrun, Variational Shape Approximation, Computer Aided Geometric Design, 23, 905-914 (2004)
\bibitem{Eppstein:2008:MGC}
    David Eppstein and Michael T. Goodrich and Ethan Kim and Rasmus Tamstorf, Motorcycle Graphs: Canonical Quad Mesh Partitioning, Computer Graphics Forum, 27, 1477-1486 (2008)
\bibitem{Bommes:2009:MIQ}
    David Bommes and Henrik Zimmer and Leif Kobbelt, Mixed-Integer Quadrangulation, ACM Transactions on Graphics, 28, 77 (2009)
\bibitem{Bommes:2011:GSO}
    David Bommes and Timm Lempfer and Leif Kobbelt, Global Structure Optimization of Quadrilateral Meshes, Computer Graphics Forum, 30, 375-384 (2011)
\bibitem{Bommes:2013:IMRQM}
    David Bommes and Marcel Campen and Hans-Christian Ebke and Pierre Alliez and Leif Kobbelt, Integer-Grid Maps for Reliable Quad Meshing, ACM Transactions on Graphics 32, 4, Proc. SIGGRAPH 2013
\bibitem{Bommes:2013:QGP}
	David Bommes and Bruno L{\'e}vy and Nico Pietroni and Enrico Puppo and Claudio Silva and Marco Tarini and Denis Zorin,
	Quad-Mesh Generation and Processing: A Survey, Computer Graphics Forum, 00, 1-26 (2013)
\bibitem{Gunpinar:2013:GBP}
    Erkan Gunpinar and Hiromasa Suzuki and Yutaka Ohtakea and Masaki Moriguchi, Generation of Bi-monotone Patches from Quadrilateral Mesh for Reverse Engineering, Computer-Aided Design, 45, 440-450 (2013)
\bibitem{Wu:2005:SRH}
    Jianhua Wu and Leif Kobbelt, Structure Recovery via Hybrid Variational Surface Approximation, Computer Graphics Forum, 24, 277-284 (2005)
\bibitem{Tierny:2012:IQRA}
    Julien Tierny and Joel Daniels II and Luis Gustavo Nonato and Valerio Pascucci and Cl{\'a}udio T. Silva,
    Interactive Quadrangulation with Reeb Atlases and Connectivity Textures, IEEE Transactions on Visualization and Computer Graphics, 18, 1650-1663 (2012)
\bibitem{Vieira:2005:SMS}
    Miguel Vieira and Kenji Shimada, Surface Mesh Segmentation and Smooth Surface Extraction through Region Growing, Computer Aided Geometric Design, 22, 771-792 (2005)
\bibitem{Tarini:2011:SQD}
    Marco Tarini and Enrico Puppo and Daniele Panozzo and Nico Pietroni and Paolo Cignoni, Simple Quad Domains for Field Aligned Mesh Parametrization, ACM Transactions on Graphics, 30, 142 (2011)
\bibitem{Campen:2012:SQD}
    Marcel Campen and David Bommes and Leif Kobbelt, Dual Loops Meshing: Quality Quad Layouts on Manifolds, ACM Transactions on Graphics, 31, 110:1-110:11 (2012)
\bibitem{Benko:2002:DSS}
    P{\'a}l Benk{$\ddot{o}$} and Tanm{\'a}s V{\'a}rady, Direct Segmentation of Smooth, Multiple Point Regions, Geometric Modeling and Processing Proceedings, 22, 169-178 (2002)
\bibitem{Li:2011:SOQME}
    Yufei Li and Wenping Wang and Ruotian Ling and Changhe Tu, Shape optimization of quad mesh elements, Computers and Graphics, 35, 444-451 (2011)

\end{thebibliography}

\end{document}
